package sf.sort;

public class CountingSort implements Sort{
    @Override
    public void sort(int[] unsorted) {
        // 计算排序，弄一个大数组，按照值存入
        // 先计算最小和最大值
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i : unsorted) {
            min = Math.min(min, i);
            max = Math.max(max, i);
        }
        int[] counts = new int[max - min + 2];
        // 先将数放入
        for (int i : unsorted) {
            counts[i - min] ++;
        }
        // 再累加
        for (int i = 0; i < counts.length - 1; i++) {
            counts[i+1] += counts[i];
        }
        // 计数完成，填充数据
        int[] sorted = new int[unsorted.length];
        for (int i : unsorted) {
            sorted[-- counts[i - min]] = i;
        }
        for (int i = 0; i < unsorted.length; i++) {
            unsorted[i] = sorted[i];
        }
    }
}
